#pragma once

#include<iostream>
#include<vector>

using namespace std;

namespace Alpaca
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
			:_bits(N / 8 + 1)
		{}

		void set(int n)
		{
			int i = n / 8;
			int j = n % 8;
			_bits[i] |= (1 << j);
		}

		void reset(int n)
		{
			int i = n / 8;
			int j = n % 8;
			_bits[i] &= ~(1 << j);
		}

		bool test(int n)
		{
			int i = n / 8;
			int j = n % 8;
			return (_bits[i] >> j) & 1;
		}

	private:
		vector<char> _bits;
	};

	struct BKDRHash
	{
		size_t operator()(const string& s)
		{
			size_t res = 0;
			for (auto it : s)
			{
				res += it;
				res *= 31;
			}
			return res;
		}
	};

	struct APHash
	{
		size_t operator ()(const string& s)
		{
			const char* str = s.c_str();
			unsigned int hash = 0;
			int i;

			for (i = 0; *str; i++)
			{
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
				}
			}

			return (hash & 0x7FFFFFFF);
		}
	};

	struct DJBHash
	{
		size_t operator()(const string& s)
		{
			unsigned int hash = 5381;
			const char* str = s.c_str();

			while (*str)
			{
				hash += (hash << 5) + (*str++);
			}

			return (hash & 0x7FFFFFFF);
		}
	};

	template<size_t N,class K,
		class Hash1 = BKDRHash,
		class Hash2 = APHash,
		class Hash3 = DJBHash>
	class BloomFilter
	{
	public:

		void set(const K& key)
		{
			size_t len = N * _X;
			size_t hashi = Hash1()(key) % len;
			_bits.set(hashi);
			cout << hashi << " ";

			hashi = Hash2()(key) % len;
			_bits.set(hashi);
			cout << hashi << " ";

			hashi = Hash3()(key) % len;
			_bits.set(hashi);
			cout << hashi << endl;

		}

		bool test(const K& key)
		{
			size_t len = N * _X;
			size_t hashi = Hash1()(key) % len;
			if (!_bits.test(hashi)) return false;

			hashi = Hash2()(key) % len;
			if (!_bits.test(hashi)) return false;

			hashi = Hash3()(key) % len;
			if (!_bits.test(hashi)) return false;

			return true;
		}

	private:
		static const size_t _X = 4;
		bitset<N*_X> _bits;
	};

	void text_bitset()
	{
		bitset<100> bits;

		bits.set(11);
		cout << bits.test(11) << endl;
		bits.reset(11);
		cout << bits.test(11) << endl;
	}

	void text()
	{
		BloomFilter<100,string> bf;

		bf.set("string");
		bf.set("hello");
		bf.set("Alpaca");
		bf.set("nihao");
		bf.set("today");
	}
};